﻿//
// KwCombinatorics v1.5.x
// Copyright © 2009-2012 - Kasey Osborn (Kasewick@gmail.com)
// Ms-PL - Use and redistribute freely
//
// File: Combination.cs
//

using System;
using System.Collections.Generic;
using System.Text;

namespace Kw.Combinatorics
{
    /// <summary>
    /// Represents an ascending sequence of non-repeating picks from a supplied number of choices.
    /// </summary>
    /// <remarks>
    /// <para>
    /// Pick-combinations are also known as K-combinations where <em>k</em> is the number
    /// of picks from <em>n</em> number of choices. This class produces pick-combinations
    /// with ascending and nonrepeating elements.
    /// 
    /// Use the <see cref="Picks"/> property to get the number of elements (k) of a
    /// pick-combination from a possible number of <see cref="Choices"/> (k).
    /// 
    /// Use the <see cref="Rank"/> property to choose a row from an ordered table of
    /// pick-combinations.
    /// 
    /// Use the <see cref="GetEnumerator">default enumerator</see> to enumerate over all
    /// the elements of a pick-combination.
    /// 
    /// Use <see cref="Rows"/> to enumerate over an ordered table of all possible
    /// pick-combinations.
    /// 
    /// Use <see cref="AllPicks"/> to enumerate over every table of all pick values
    /// from (1..<see cref="Picks"/>).
    /// 
    /// Use the <see cref="Permute">Permute</see> method to pick objects from a supplied
    /// array of choices based on the current sequence.
    /// 
    /// Use the <see cref="P:Kw.Combinatorics.Combination.Item(System.Int32)">indexer</see>
    /// to get an element of the sequence.
    /// </para>
    /// <para>
    /// For more information about pick-combinations, see:<br />
    /// <br />
    /// <em>http://en.wikipedia.org/wiki/Combination</em>
    /// </para>
    /// </remarks>
    /// <example>
    /// <para>
    /// Iterating over all rows of <c>Combination (5, 3)</c> produces:
    /// </para>
    /// <para>
    /// { 0, 1, 2 }<br />
    /// { 0, 1, 3 }<br />
    /// { 0, 1, 4 }<br />
    /// { 0, 2, 3 }<br />
    /// { 0, 2, 4 }<br />
    /// { 0, 3, 4 }<br />
    /// { 1, 2, 3 }<br />
    /// { 1, 2, 4 }<br />
    /// { 1, 3, 4 }<br />
    /// { 2, 3, 4 }
    /// </para>
    /// </example>
    public class Combination :
        ICloneable,
        IComparable,
        System.Collections.IEnumerable,
        IComparable<Combination>,
        IEquatable<Combination>,
        IEnumerable<int>
    {
        private int[] data;     // The picks for the current rank. Length of data is 'k'.
        private int choices;    // Number of possible values 'n'.
        private long rank;      // Row index of the table of pick-combinations.

        #region Constructors

        /// <summary>
        /// Make an empty <see cref="Combination"/>.
        /// </summary>
        public Combination ()
        {
            this.data = new int[0];
            this.choices = 0;
            this.rank = 0;
            this.Height = 0;
        }


        /// <summary>
        /// Make a copy of a <see cref="Combination"/>.
        /// </summary>
        /// <param name="source">Instance to copy.</param>
        /// <exception cref="ArgumentNullException">When <em>source</em> is <b>null</b>.</exception>
        public Combination (Combination source)
        {
            if (source == null)
                throw new ArgumentNullException ("source");

            this.data = new int[source.data.Length];
            source.data.CopyTo (this.data, 0);
            this.choices = source.choices;
            this.rank = source.rank;
            this.Height = source.Height;
        }


        /// <summary>
        /// Make a new <see cref="Combination"/> of all picks from the
        /// supplied number of choices.
        /// </summary>
        /// <param name="choices">Number of elements in the new <see cref="Combination"/>.</param>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When <em>choices</em> less than 0.
        /// </exception>
        public Combination (int choices)
        {
            if (choices < 0)
                throw new ArgumentOutOfRangeException ("choices", "Value is less than zero.");

            this.choices = choices;
            this.Height = choices == 0? 0 : 1;
            this.rank = 0;

            this.data = new int[choices];
            for (int j = 0; j < Picks; ++j)
                this.data[j] = j;
        }


        /// <summary>
        /// Make a new <see cref="Combination"/> of <see cref="Rank"/> 0 from the supplied
        /// <em>choices</em> and <em>picks</em>.
        /// </summary>
        /// <param name="choices">Number of values to pick from.</param>
        /// <param name="picks">Number of elements chosen.</param>
        /// <example>
        /// <code source="Examples\CombinationExample01\CombinationExample01.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When negative value supplied; when <em>picks</em> greater than <em>choices</em>.
        /// </exception>
        /// <exception cref="OverflowException">When the numbers are just too big.</exception>
        public Combination (int choices, int picks)
        {
            if (choices < 0)
                throw new ArgumentOutOfRangeException ("choices", "Value is less than zero.");

            if (picks < 0)
                throw new ArgumentOutOfRangeException ("picks", "Value is less than zero.");

            if (picks > choices)
                throw new ArgumentOutOfRangeException ("picks", "Value is greater than choices.");

            this.choices = choices;
            this.Height = picks == 0? 0 : BinomialCoefficient (choices, picks);
            this.rank = 0;

            this.data = new int[picks];
            for (int j = 0; j < picks; ++j)
                this.data[j] = j;
        }


        /// <summary>
        /// Make a new combination of the supplied <em>rank</em> from the supplied
        /// <em>choices</em> and <em>picks</em>.
        /// </summary>
        /// <remarks>
        /// Rank may be any integer value.  If the supplied <em>Rank</em> is out of range of
        /// (0..<see cref="Height"/>-1), it will be normalized.  For example, a value of -1 will
        /// produce the last <see cref="Combination"/> row in the ordered table.
        /// </remarks>
        /// <param name="choices">Number of values to pick from.</param>
        /// <param name="picks">Width of the selected sequence.</param>
        /// <param name="rank">Initial row index of the ordered <see cref="Combination"/> table.</param>
        /// <example>
        /// <code source="Examples\CombinationExample01\CombinationExample01.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When negative value supplied; when <em>picks</em> greater than <em>choices</em>.
        /// </exception>
        /// <exception cref="OverflowException">When too many <em>choices</em>.</exception>
        public Combination (int choices, int picks, long rank)
        {
            if (choices < 0)
                throw new ArgumentOutOfRangeException ("choices", "Value is less than zero.");

            if (picks < 0)
                throw new ArgumentOutOfRangeException ("picks", "Value is less than zero.");

            if (picks > choices)
                throw new ArgumentOutOfRangeException ("picks", "Value is greater than choices.");

            this.data = new int[picks];
            this.choices = choices;
            this.Height = picks == 0? 0 : BinomialCoefficient (choices, picks);
            Rank = rank;
        }

        #endregion

        #region Properties

        /// <summary>
        /// Enumerate over all rows of all <see cref="Combination"/> tables for every number
        /// of elements from (1..<see cref="Picks"/>).
        /// </summary>
        /// <example>
        /// <code source="Examples\CombinationExample02\CombinationExample02.cs" lang="cs" />
        /// </example>
        /// <seealso cref="Permute"/>
        public IEnumerable<Combination> AllPicks
        {
            get
            {
                for (int k = 1; k <= Picks; ++k)
                {
                    Combination current = (Combination) MemberwiseClone ();

                    current.data = new int[k];
                    current.Height = BinomialCoefficient (choices, k);
                    current.Rank = 0;

                    foreach (Combination result in current.Rows)
                        yield return result;
                }
            }
        }


        /// <summary>
        /// The number of integers to pick from.
        /// </summary>
        public int Choices
        { get { return choices; } }


        /// <summary>
        /// Number of elements in the <see cref="Combination"/>.
        /// </summary>
        public int Picks
        { get { return data.Length; } }


        /// <summary>
        /// Total count of distinct sequences in the <see cref="Combination"/> table.
        /// </summary>
        public long Height
        { get; private set; }


        /// <summary>
        /// Row index of the ordered <see cref="Combination"/> table.
        /// </summary>
        /// <remarks>
        /// Any assigned value out of range will be normalized to (0..<see cref="Height"/>-1).
        /// </remarks>
        /// <example>
        /// <code source="Examples\CombinationExample03\CombinationExample03.cs" lang="cs" />
        /// </example>
        public long Rank
        {
            get
            {
                return rank;
            }
            set
            {
                if (Height == 0)
                    rank = 0;
                else
                {
                    // Normalize the new rank.
                    rank = value % Height;
                    if (rank < 0)
                        rank += Height;

                    //
                    // Perform unranking:
                    //

                    long diminishingRank = Height - rank - 1;
                    int combinaticAtom = choices;

                    for (int k = Picks; k > 0; --k)
                        for (; ; )
                        {
                            --combinaticAtom;

                            int trialCount = (int) BinomialCoefficient (combinaticAtom, k);
                            if (trialCount <= diminishingRank)
                            {
                                diminishingRank -= trialCount;
                                data[Picks - k] = choices - 1 - combinaticAtom;
                                break;
                            }
                        }
                }
            }
        }


        /// <summary>
        /// Enumerate over all rows of the <see cref="Combination"/> table for every value
        /// of <see cref="Rank"/>.
        /// </summary>
        /// <remarks>
        /// If the start row is not <see cref="Rank"/> 0, the enumeration will wrap around
        /// so that <see cref="Height"/> items are always produced.
        /// </remarks>
        /// <example>
        /// <code source="Examples\CombinationExample01\CombinationExample01.cs" lang="cs" />
        /// </example>
        public IEnumerable<Combination> Rows
        {
            get
            {
                if (Height > 0)
                {
                    long startRank = rank;
                    for (Combination current = (Combination) MemberwiseClone (); ; )
                    {
                        yield return current;
                        current.Rank = current.Rank + 1;
                        if (current.Rank == startRank)
                            break;
                    }
                }
            }
        }


        /// <summary>
        /// Get a element of the <see cref="Combination"/> at the supplied column.
        /// </summary>
        /// <param name="index">Zero-based index value.</param>
        /// <returns>Sequence value at <em>index</em>.</returns>
        /// <example>
        /// <code source="Examples\CombinationExample03\CombinationExample03.cs" lang="cs" />
        /// </example>
        /// <exception cref="IndexOutOfRangeException">
        /// When <em>index</em> not in range (0..<see cref="Picks"/>-1).
        /// </exception>
        public int this[int index]
        { get { return data[index]; } }

        #endregion

        #region Member methods

        /// <summary>Make a copy of this <see cref="Combination"/>.</summary>
        /// <remarks>Implements the deprecated <see cref="System.ICloneable"/> interface.</remarks>
        /// <returns>Copy of the object.</returns>
        public object Clone ()
        { return new Combination (this); }


        /// <summary>Compare two <see cref="Combination"/>s.</summary>
        /// <param name="obj">Target of the comparison.</param>
        /// <returns>A signed integer indicating the sort order of this instance to <em>obj</em>.</returns>
        public int CompareTo (object obj)
        { return CompareTo (obj as Combination); }


        /// <summary>Compare two <see cref="Combination"/>s.</summary>
        /// <param name="other">Target of the comparison.</param>
        /// <returns>A signed integer indicating the sort order of this instance to <em>other</em>.</returns>
        public int CompareTo (Combination other)
        {
            if ((object) other == null)
                return 1;

            int result = this.Picks - other.Picks;
            if (result == 0)
            {
                result = this.Choices - other.Choices;
                if (result == 0)
                {
                    long rankDiff = this.Rank - other.Rank;

                    if (rankDiff == 0)
                        result = 0;
                    else
                        result = rankDiff < 0 ? -1 : 1;
                }
            }

            return result;
        }


        /// <summary>
        /// Indicate whether two <see cref="Combination"/>s have the same value.
        /// </summary>
        /// <param name="obj">Target of the comparison.</param>
        /// <returns>
        /// <b>true</b> if <em>obj</em> has the same value as this object; otherwise, <b>false</b>.
        /// </returns>
        public override bool Equals (object obj)
        { return Equals (obj as Combination); }


        /// <summary>
        /// Indicate whether two <see cref="Combination"/>s have the same value.
        /// </summary>
        /// <param name="other">Target of the comparison.</param>
        /// <returns>
        /// <b>true</b> if <em>other</em> has the same value as this instance; otherwise, <b>false</b>.
        /// </returns>
        public bool Equals (Combination other)
        {
            return (object) other != null
                && other.Rank == Rank && other.Choices == Choices && other.Picks == Picks;
        }


        /// <summary>Get an object-based enumerator of the elements.</summary>
        /// <returns>object-based elemental enumerator.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()
        { return this.GetEnumerator (); }


        /// <summary>Enumerate over all elements of a <see cref="Combination"/>.</summary>
        /// <returns>An <c>IEnumerator&lt;int&gt;</c> for this <see cref="Combination"/>.</returns>
        /// <example>
        /// <code source="Examples\CombinationExample05\CombinationExample05.cs" lang="cs" />
        /// </example>
        public IEnumerator<int> GetEnumerator ()
        {
            for (int index = 0; index < data.Length; index++)
                yield return data[index];
        }


        /// <summary>Get the hash oode of the <see cref="Combination"/>.</summary>
        /// <returns>A 32-bit signed integer hash code.</returns>
        public override int GetHashCode ()
        { return unchecked ((int) Rank); }


        /// <summary>
        /// Provide a readable form of the <see cref="Combination"/> sequence.
        /// </summary>
        /// <remarks>Result is enclosed in braces and separated by commas.</remarks>
        /// <returns>A <c>string</c> that represents the sequence.</returns>
        /// <example>
        /// <code source="Examples\CombinationExample03\CombinationExample03.cs" lang="cs" />
        /// </example>
        public override string ToString ()
        {
            if (Height == 0)
                return ("{ }");

            StringBuilder result = new StringBuilder ("{ ");

            for (int i = 0; ; )
            {
                result.Append (this[i]);

                ++i;
                if (i >= Picks)
                    break;

                result.Append (", ");
            }

            result.Append (" }");

            return result.ToString ();
        }

        #endregion

        #region Static methods

        /// <summary>
        /// Apply a <see cref="Combination"/> sequence to rearrange the supplied list or array.
        /// </summary>
        /// <typeparam name="T">Type of items to rearrange.</typeparam>
        /// <param name="arrangement">New arrangement for items.</param>
        /// <param name="source">List of items to rearrange.</param>
        /// <returns>List of rearranged items.</returns>
        /// <example>
        /// <code source="Examples\CombinationExample04\CombinationExample04.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentNullException">
        /// When <em>arrangement</em> or <em>source</em> is <b>null</b>.
        /// </exception>
        /// <exception cref="ArgumentException">
        /// When length of <em>source</em> is less than <see cref="Picks"/>.
        /// </exception>
        public static List<T> Permute<T> (Combination arrangement, IList<T> source)
        {
            if (arrangement == null)
                throw new ArgumentNullException ("arrangement");

            if (source == null)
                throw new ArgumentNullException ("source");

            if (source.Count < arrangement.Choices)
                throw new ArgumentException ("Not enough supplied values.", "source");

            List<T> result = new List<T> (arrangement.Picks);

            for (int i = 0; i < arrangement.Picks; ++i)
                result.Add (source[arrangement.data[i]]);

            return result;
        }

        
        /// <summary>Indicate whether two <see cref="Combination"/>s are equal.</summary>
        /// <param name="param1">A <see cref="Combination"/> sequence.</param>
        /// <param name="param2">A <see cref="Combination"/> sequence.</param>
        /// <returns><b>true</b> if supplied sequences are equal;
        /// otherwise, <b>false</b>.</returns>
        public static bool operator == (Combination param1, Combination param2)
        {
            if ((object) param1 == null)
                return (object) param2 == null;
            else
                return param1.Equals (param2);
        }


        /// <summary>Indicate whether <see cref="Combination"/>s are not equal.</summary>
        /// <param name="param1">A <see cref="Combination"/> sequence.</param>
        /// <param name="param2">A <see cref="Combination"/> sequence.</param>
        /// <returns><b>true</b> if supplied sequences are not equal;
        /// otherwise, <b>false</b>.</returns>
        public static bool operator != (Combination param1, Combination param2)
        { return !(param1 == param2); }


        /// <summary>Indicate whether the left <see cref="Combination"/> is less than
        /// the right <see cref="Combination"/>.</summary>
        /// <param name="param1">A <see cref="Combination"/> sequence.</param>
        /// <param name="param2">A <see cref="Combination"/> sequence.</param>
        /// <returns><b>true</b> if the left sequence is less than
        /// the right sequence; otherwise, <b>false</b>.</returns>
        public static bool operator < (Combination param1, Combination param2)
        {
            if ((object) param1 == null)
                return (object) param2 != null;
            else
                return param1.CompareTo (param2) < 0;
        }


        /// <summary>Indicate whether the left <see cref="Combination"/> is greater than
        /// or equal to the right <see cref="Combination"/>.</summary>
        /// <param name="param1">A <see cref="Combination"/> sequence.</param>
        /// <param name="param2">A <see cref="Combination"/> sequence.</param>
        /// <returns><b>true</b> if the left sequence is greater than or equal to
        /// the right sequence; otherwise, <b>false</b>.</returns>
        public static bool operator >= (Combination param1, Combination param2)
        { return !(param1 < param2); }


        /// <summary>Indicate whether the left <see cref="Combination"/> is greater than
        /// the right <see cref="Combination"/>.</summary>
        /// <param name="param1">A <see cref="Combination"/> sequence.</param>
        /// <param name="param2">A <see cref="Combination"/> sequence.</param>
        /// <returns><b>true</b> if the left sequence is greater than
        /// the right sequence; otherwise, <b>false</b>.</returns>
        public static bool operator > (Combination param1, Combination param2)
        {
            if ((object) param1 == null)
                return false;
            else
                return param1.CompareTo (param2) > 0;
        }


        /// <summary>Indicate whether the left <see cref="Combination"/> is less than or equal
        /// to the right <see cref="Combination"/>.</summary>
        /// <param name="param1">A <see cref="Combination"/> sequence.</param>
        /// <param name="param2">A <see cref="Combination"/> sequence.</param>
        /// <returns><b>true</b> if the left sequence is less than or equal to
        /// the right sequence; otherwise, <b>false</b>.</returns>
        public static bool operator <= (Combination param1, Combination param2)
        { return !(param1 > param2); }


        /// <summary>
        /// Increment the <see cref="Rank"/> of the supplied <see cref="Combination"/> by 1.
        /// The increment operator can appear before or after its operand.
        /// </summary>
        /// <param name="param">A <see cref="Combination"/> to modify.</param>
        /// <returns>The supplied <see cref="Combination"/> with the next higher rank.</returns>
        /// <exception cref="ArgumentNullException">When <em>param</em> is <b>null</b>.</exception>
        public static Combination operator ++ (Combination param)
        {
            if (param == null)
                throw new ArgumentNullException ("param");

            param.Rank = param.Rank + 1;
            return param;
        }


        /// <summary>
        /// Decrement the <see cref="Rank"/> of the supplied <see cref="Combination"/> by 1.
        /// The decrement operator can appear before or after its operand.
        /// </summary>
        /// <param name="param">A <see cref="Combination"/> to modify.</param>
        /// <returns>The supplied <see cref="Combination"/> with the previous lower rank.</returns>
        /// <exception cref="ArgumentNullException">When <em>param</em> is <b>null</b>.</exception>
        public static Combination operator -- (Combination param)
        {
            if (param == null)
                throw new ArgumentNullException ("param");

            param.Rank = param.Rank - 1;
            return param;
        }


        /// <summary>
        /// Perform binomial coefficient calculation.
        /// </summary>
        /// <param name="n">Number of choices.</param>
        /// <param name="k">Number of picks.</param>
        /// <returns>
        /// Total number of possible <see cref="Combination"/>s for the given choices and picks.
        /// </returns>
        /// <remarks>
        /// A binomial coeffecient is a row (<em>n</em>) and column (<em>k</em>) of Pascal's
        /// triangle and is also the number of rows in a pick-combination table.
        /// For the special case where <em>k</em> is 0, the number of rows of a
        /// <see cref="Combination"/> table is considered by this library to be 0 instead
        /// of the returned value of 1.
        /// </remarks>
        /// <exception cref="OverflowException">When the numbers are just too big.</exception>
        /// <exclude />
        static public long BinomialCoefficient (int n, int k)
        {
            if (k < 0 || k > n)
                return 0;

            System.Diagnostics.Debug.Assert (k <= n);

            // Formula is n!/(k!(n-k)!)
            // When n>20, n! overflows.  So do this voodoo instead:

            int x = k > n - k ? k : n - k;
            int y = n - x;
            int b = y;

            long v1 = 1;
            for (int i = x + 1; i <= n; ++i)
            {
                if (i > y * 2 || i % 2 != 0)
                    v1 = checked (v1 * i);
                else
                {
                    v1 = checked (v1 * 2);
                    --b;
                }
            }

            return v1 / Permutation.Factorial (b);
        }

        #endregion
    }
}
